package main

func main() {
	maxDistance([][]int{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}})
}

/**
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，
并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」
（ Manhattan Distance）：(x0, y0) 和 (x1, y1)
这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
*/

/*
*
说白了就是看哪个位置上的海洋离陆地最远
*/
var direction = []position{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

type position struct {
	x, y int
}

func maxDistance(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	queue := []position{}
	visit := make([][]int, m)
	for i := 0; i < m; i++ {
		visit[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				visit[i][j] = 1
				queue = append(queue, position{i, j})
			}
		}
	}
	var depth int
	// 全是陆地，没有海洋直接返回
	if len(queue) == m*n {
		return -1
	}
	// 如果队列中还有值说明还可以继续广搜
	for len(queue) > 0 {
		newQueue := []position{}
		for i := 0; i < len(queue); i++ {
			cur := queue[i]
			// 四个方向都要搜索
			for _, v := range direction {
				next := position{v.x + cur.x, v.y + cur.y}
				// 遍历到的地方把海洋设置陆地
				// visit 置1
				// 加入队列中
				if next.x < m &&
					next.y < n &&
					next.x > -1 &&
					next.y > -1 &&
					visit[next.x][next.y] == 0 &&
					grid[next.x][next.y] == 0 {
					grid[next.x][next.y] = 1
					visit[next.x][next.y] = 1
					newQueue = append(newQueue, next)
				}
			}
		}
		// 每层遍历结束，深度都加1
		depth++
		queue = newQueue
	}
	return depth
}
